The present invention relates to a fast and economical Hadamard transform device which can be easily implemented with conventional components.
In processing analog signals such as video or acoustic signals, orthogonal transforms such as fast Fourier transform (FFT) or fast Walsh Hadamard transform (FWHT) have been widely used and various algorithms for performing such transforms have been also devised and demonstrated with satisfactory results. However, fast computation speed and economy are not compatible in practice; that is, one must be sacrificed for the other.
Speech recognition devices which need the processing of analog signals comprises, for instance, a characteristic pattern pickup stage or a stage for analyzing an input speech signal, a standard pattern storage or a class of templates, a matching or comparison stage and a decision stage. The characteristic pattern pickup stage or input-sound analyzing stage converts the sound of the input into time-serial characteristic vectors. The standard pattern storage has time-serial character vectors of the sounds to be classified. The matching or comparison stage compares the time-serially converted or transformed input sound pattern with the standard patterns to find out the similarity or calculate the distance between them. The decision stage picks up the template which has the highest similarity of the input sound or the shortest distance to the input sound thereby classifying the input sound.
In order to analyze or pick up the feature of an input sound, the so-called filter-bank method, the orthogonal transform such as FFT, the linear predictive analysis or autoregressive analysis has been widely used. The Hadamard transform can be used for the input sound analysis because it does not need high speed computation and devices for performing fast Hadamard transforms can be easily implemented in the form of LSIs.
An example of the fast Walsh Hadamard Transform of order n=2.sup.m, where m=1, 2, . . . , is expressed by ##EQU1##
One of the features or characteristics of this algorithm resides in the fact that values of the k-th transforms X.sub.k (i) and X.sub.k (j) can be derived from the preceding transform step by the rules of EQU X.sub.k (i)=X.sub.k-1 (i)+X.sub.k-1 (j)
and EQU X.sub.k (j)=X.sub.k-1 (i)-X.sub.k-1 (j).
After the X.sub.k (i) and X.sub.k (j) have been obtained, X.sub.k-1 (i) and X.sub.k-1 (j) will not be used again; that is, they can be discarded. As a result, the contents in the storage location in which X.sub.k-1 (i) or X.sub.k-1 (j) has been stored can be modified to X.sub.k (i) or X.sub.k (j). To put into another way, one storage location can be used for storing either X.sub.k-1 (i) or X.sub.k-1 (j), or X.sub.k (i) or X.sub.k-1 (j). It follows, therefore, that it suffices to provide only the number of n storage locations for performing Walsh Hadamard transforms.
Another algorithm having a similar feature is ##EQU2##
One of the problems encountered in the design of devices capable of performing such algorithms as described above is that in the case of read and write cycles of respective transform steps, an efficient and accurate addressing method must be provided.